The subject invention relates to a method of generating test sequences for digital circuits.
Prior art methods of test sequence generation are described in FAULT TOLERANT COMPUTING Theory and Techniques, Volume 1, Chapter 1, 1.4.2 "Stuck at Fault Testing," published by Prentice-Hall, Englewood, N.J.; and M. H. Schulz and E. Auth: "ESSENTIAL": An Effective Self-Learning Test Pattern Generation Algorithm for Sequential Circuits, Proc. Int. Test Conf., pp. 28-37, August 1989; and their referenced documents.
We shall now explain, utilizing the figures, the prior art in the test sequence generation method with which the subject invention is concerned.
The prior art relating to test sequence methods for sequential circuits includes such methods as the iterative array method as shown in FIG. 9; the method of state justification after determining the fault propagation path, shown in FIG. 10; and, a method of simultaneously determining the fault propagation path and state justification in reverse direction to the time axis.
FIG. 9 is a conceptual figure of a sequential circuit which is transformed into an iterative array. One cell of this array is called a time frame.
In FIG. 9, 901 represents time frame 0, 911 represents time frame 1 and 921 represents time frame i. In time frame 0, 902 represents the combinational circuit, 903 represents the memory elements, and 904, 905, 906 and 907 represent, respectively, the primary inputs, pseudo primary inputs, primary outputs and pseudo primary outputs. In time frame 1, 912 represents the combinational circuit, 913 represents the memory elements, and 914, 915, 916 and 917 represent, respectively, the primary inputs, pseudo primary inputs, primary outputs, and, pseudo primary outputs. 922 represents the combinational circuit in time frame i, 923 represents the memory elements, and 924, 925, 926 and 927, respectively, represent the primary inputs, pseudo primary inputs, primary outputs and pseudo primary outputs.
In the iterative array method, by replacing a temporal expansion with a spatial expansion in the circuit under consideration, the circuit under consideration is entirely represented by combinational logic. In the circuit, the target fault is handled as multiple fault and, the test pattern generation algorithm for the combinational logic is applied in the iterative array.
As shown by the flow chart diagram in FIG. 10, the method of state justification after determining the fault propagation path, consists of commencing processing at step 1001. The fault propagation path is determined at step 1002 on the basis of testability costs. Then at step 1003, the greatest time frame's unjustified signal line is justified. At step 1004, a determination is made as to whether there are unjustified signal lines, and if there are unjustified signal lines, the time axis is followed in a reverse direction at step 1005, and processing returns to step 1003. If there are no unjustified signal lines, processing advances to step 1006 and the test sequence generation is terminated.
As shown by the flow chart in FIG. 11, the method of simultaneously determining the fault propagation path and undertaking state justification in reverse sequence to the time axis, starts processing at step 1102. If the fault propagation path is not complete, a path is sought from the location of the fault or from the pseudo primary input to the primary output. Alteratively, a path is sought to the pseudo primary output which corresponds to the flip-flop located at the pseudo primary input at the next time frame which is equivalent to the fault signal. Also, a value is allocated to the pseudo primary output which corresponds to the flip-flop which is equivalent to the pseudo primary input at the next time frame, where unjustified signal lines will exist. These unjustified signal lines will then have their state justified.
In the event that test sequence generation had not been completed at the time of the test at step 1103, the processing proceeds to step 1104, the time frame is replaced by the next time frame, and processing reverts to step 1102. If the test sequence had been generated at the time of test at step 1103, the process branches to step 1105 and test sequence generation is completed.
However, the prior art methods have the following problems:
(1) If sufficient fault coverage is not obtained as a result of test sequence generation, it will be necessary to modify the design itself to facilitate testing. In particular, if a partial scan design is to be adopted, it is vital to determine which memory element will be scanned in order to detect the large number of faults which were undetected by the result of test sequence generation. However, in the prior art methods, it is difficult in the process of test sequence generation to obtain data to indicate which memory element should be scanned if processing was aborted due to computing time limitation, etc.
For example, in the iterative array method, since a plurality of time frames are simultaneously processed in the iterative array, unjustified signal lines and fault effects are scattered over time frames at that point in time when processing was aborted. Thus, it is difficult to immediately obtain data which is useful for selecting the memory elements which should be scanned.
In the method which justifies the state after determining the fault propagation path, and in the method of simultaneously determining the fault propagation path and justifying the state in reverse direction to the time axis, there are times when the fault propagation path from the point of fault to the primary output has not been justified at the time when processing was aborted. In such case, data useful for the selection of memory elements which should be scanned cannot be obtained.
(2) A large amount of time is required for fault propagation processing. The difficulty of selecting a path where fault propagation is easy, and, the sensitization of fault propagation paths for each and every fault can be cited as reasons why time is required for fault propagation processing.
For example, in the iterative array method, at each gate in the iterative array, the propagation of fault signals takes place by forward processing. If the path selection was unsuitable, backtracking takes place in accordance with the allocation of values made at each and every gate with consequent use of computation time.
In the method which undertakes state justification after determining the fault propagation path, if the initial path selection was unsuitable, many backtracks will be necessary in attempting to sensitize paths which are difficult to sensitize. Thus, the time for test sequence generation becomes extremely long. In these methods, as well as in the method of simultaneously undertaking the determination of the fault propagation path and state justification in reverse direction of the time axis, it is necessary to select the fault propagation path or to carry out fault propagation operations for each and every fault. They both require large amounts of computing time.
(3) There is no measurement to accurately represent the difficulty of generating the rise and fall signals. In the prior art methods, when using the heuristic technique, there is no measurement for testability which directly reflects the degree of difficulty in generating rise and fall in relation to the clocking operation.
Since the difficulties in controlling to 0 and in controlling to 1 were used to represent the difficulties of the rise and fall operations, efficiency was sometimes poor. For instance, in a dual input exclusive OR, it is easy to create rise and fall operations for one input, it is then easy to generate rise or fall signals at the output regardless of whether the other value is 0 or 1. Yet, according to the prior art computation methods, the difficulty of generating the output's rise or fall signal was represented by the difficulty in generating 0 for the output and 1 for the output. Thus, it was treated as being difficult even when it was actually easy to generate rise and fall signals. Therefore, there were times when effort was expended in assigning rise and fall signals to other signal lines in cases where it was difficult to generate rise and fall signals. At these times, the efficiency of test input generation was degraded.
(4) It is difficult to deal with fault signals entering the memory element's control input. At such time as when the fault propagation path includes a path from the control input of the memory element through the output of the memory element, differences have to be created at the control input of the memory element by the existence or the non-existence of the rise or fall signals. In addition, fault propagation is undertaken to transmit the existence or the non-existence of a fault to the output. At such times, the amount of required memory is increased since it is necessary to consider a plurality of time frames simultaneously. Hence, the efficiency of test sequence generation is decreased because a plurality of time frames must be managed.
(5) It is difficult to handle reconvergent clock signals. In the prior art methods, if the clock signal is branched and reconverged after passing through a varying number of time frames, it may be difficult to make the iterative array itself. Or, even if the iterative array is made, backtracking which spans time frames may take place due to demand inconsistencies, so that the efficiency of test sequence generation is decreased. For example, in the iterative array method, if there are memory elements in the reconvergence path, there are times when the number of time frames in the reconvergence path do not match. In these situations, it is difficult to make an iterative array model.
In the method of conducting state justification after determining the fault propagation path, and in the method of simultaneously determining the fault propagation path and justifying the state in reverse direction of the time axis, the processing assumes state allocation will be done independently. This assumption is made despite the fact that, actually, the status of the lines on a reconvergent path are mutually dependent. Therefore, inconsistences are generated at the reconvergent point, decreasing the efficiency of test sequence generation.
(6) Computing time is required for state justification. In the prior art methods, it was necessary to perform state justification for test sequence generation for every fault. Thus, large amounts of computing time were required.